#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string.h>
// 求数组长度
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
// 交换数组中的两个元素
#define SWAP(arr, i, j ) {			\
	int tmp = arr[i];			\
	arr[i] = arr[j];			\
	arr[j] = tmp;			\
}

/*
	查找目标值第一次出现的下标
	思路是什么呢?
	1.仍然要先进行简单二分查找,先找到目标值的下标
	2.但是现在找到后,不能直接返回,除非确定它是第一次该目标值第一次出现的下标
	
	我究竟怎么确定这个下标是目标值第一次出现呢?
	1.该索引已经是当前折半区间的左起点,左边已经没有元素了,那么它必然是第一个
	2.如果左边的一个元素已经比找到的元素小了,也能够确定是第一次出现


	查找目标值最后一次出现的下标:
	思路是什么呢?
	1.仍然要先进行简单二分查找,先找到目标值的下标
	2.但是现在找到后,不能直接返回,除非确定它是最后一次该目标值出现的下标

	我究竟怎么确定这个下标是目标值最后一次出现呢?
	1.该索引已经是当前折半区间的右边界,右边已经没有元素了,那么它必然是最后一个
	2.如果右边的一个元素已经比找到的元素大了,也能够确定是最后一次出现

*/
int search_first(int arr[], int len, int target) {
	int left = 0, right = len - 1;	// 循环折半的左右区间
	while (left <= right) {	
		int mid = left + (right - left >> 1);
		int diff = target - arr[mid];
		if (diff > 0) {
			// 循环的去查找右边区间,左半区间丢弃,要改left
			left = mid + 1;
		}
		else if (diff < 0) {
			// 循环的去查找左边区间,右半区间丢弃,要改right
			right = mid - 1;
		}
		else {
			// 找到了目标值,但是还不能确定它是一次出现的下标
			// 于是就进行判断
			if (mid == left || arr[mid - 1] < target) {
				// 确定mid是target第一次出现的下标
				return mid;
			}
			// 不能确定是第一次出现,继续向左半区间找,丢弃右半区间
			right = mid - 1;
		}
	}
	// 循环都结束了,还没有return 说明目标值不存在
	return -1;
}

int main(void) {
	int arr[] = { 1,2,3,4,5,6,10,10,10,10,10,10,11,12,13,15,17,19,20 };
	int ret = search_first(arr, ARR_LEN(arr), 10);
	return 0;
}